• Virtual Judge
• ZeroJudge

題意

• 輸入兩字串 S1、S2，問是否能找出對兩字串皆合法的 L？
• 需要注意的點有：
  1. 會先輸入一正整數 N 代表測資數
  2. 每兩行輸入為一筆測資
  3. 每筆測資的 S1、S2 皆為二進位字串
  4. 每行輸入不超過 30 個字元
  5. 所有輸入皆為合法字串
     • 開頭不為 0
     • 至少兩位元
  6. 什麼是合法的 L？
     • 重複 S - L (二進位減法) 直到 S = L
  7. 輸出格式
     • p 代表第幾筆測資
     • Pair #p: All you need is love!
     • Pair #p: Love is not all you need!

解法

• 思路
  • 一直重複用 S - L，其實就是看 S 是不是 L 的倍數，題目有舉例：

  S = 11011 = 27
  L =    11 =  3
  
    bin   dec
  11011 =  27
  11000 =  24
  10101 =  21
  10010 =  18
   1111 =  15
   1100 =  12
   1001 =   9
    110 =   6
     11 =   3
  

  • 所以要檢查有沒有一數字同時對兩字串 S1、S2 都合法，代表 L 要同時為兩者的公因數，所以用 GCD 檢查兩者是否互質 (GCD = 1)；先把輸入轉成十進位比較好處理
• 老套路，輸入測資數 N 後，用 while 迴圈重複讀入兩字串存到字元陣列裡

  int N;
  
  scanf("%d", &N);
  
  while(N--){
  
      char S1[31] = {0};
      char S2[31] = {0};
  
      scanf("%s%s", S1, S2);
  
      ...
  }
  

• 把字串代表的二進位轉成十進位

  int str_to_int(char *a, char *b){
  
      int num1 = 0, num2 = 0;
      int i;
  
      for(i = 0; i < strlen(a); i++){
          num1 = (num1 << 1) + (a[i] - '0');
      }
  
      for(i = 0; i < strlen(b); i++){
          num2 = (num2 << 1) + (b[i] - '0');
      }
  
      return GCD(num1, num2);
  }
  

• 跟上篇 Day 0x7 UVa11417 GCD 一樣用個邪教遞迴

  int GCD(int a, int b){
      return b == 0 ? a : GCD(b, a % b);
  }
  

• 判斷回傳是不是互質，再照規則輸出即可

  if(str_to_int(S1, S2) != 1){
      printf("Pair #%d: All you need is love!\n", Case++);
  }
  else{
      printf("Pair #%d: Love is not all you need!\n", Case++);
  }
  

• C code

  #include<stdio.h>
  #include<string.h>
  
  int GCD(int a, int b){
      return b == 0 ? a : GCD(b, a % b);
  }
  
  int str_to_int(char *a, char *b){
  
      int num1 = 0, num2 = 0;
      int i;
  
      for(i = 0; i < strlen(a); i++){
          num1 = (num1 << 1) + (a[i] - '0');
      }
  
      for(i = 0; i < strlen(b); i++){
          num2 = (num2 << 1) + (b[i] - '0');
      }
  
      return GCD(num1, num2);
  }
  
  int main(){
  
      int N, Case = 1;
  
      scanf("%d", &N);
  
      while(N--){
  
          char S1[31] = {0};
          char S2[31] = {0};
  
          scanf("%s%s", S1, S2);
  
          if(str_to_int(S1, S2) != 1){
              printf("Pair #%d: All you need is love!\n", Case++);
          }
          else{
              printf("Pair #%d: Love is not all you need!\n", Case++);
          }
      }
  
      return 0;
  }
  

• C++
  • 十進位轉二進位可以用 stoi()
    • std::stoi
  • 其他也有像 dec、hex、oct 可用
    • std::dec, std::hex, std::oct
  • 最大公因數可用 gcd()，但 C++17 才支援
    • std::gcd
      
• C++ code

  #include <bits/stdc++.h>
  using namespace std;
  
  int GCD(int a, int b){
      return b == 0 ? a : GCD(b, a % b);
  }
  
  int main(){
  
      int N, Case = 1;
  
      cin >> N;
  
      while(N--){
  
          string S1, S2;
  
          cin >> S1 >> S2;
  
          int num1 = stoi(S1, nullptr, 2), num2 = stoi(S2, nullptr, 2);
  
          if(GCD(num1, num2) != 1){
              cout << "Pair #" << Case++ << ": All you need is love!\n";
          }
          else{
              cout << "Pair #" << Case++ << ": Love is not all you need!\n";
          }
      }
  
      return 0;
  }